package com.zhongge.custombintree;

import com.zhongge.binarytreeOJ.MyBinaryTree;

import java.util.*;

/**
 * @ClassName MyBinTree
 * @Description TODO 自定义二叉树
 * @Author zhongge
 * @Date 2025/9/3 10:35
 * @Version 1.0
 */
public class MyBinTree {
    public static class TreeNode{
        //数值域
        public char val;
        //左孩子
        public TreeNode left;
        //右孩子
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    //二叉树 的创建
    //////////////////////////////////////////////////////////
    /**
     * 1.手动创建二叉树
     * @return 根节点
     */
    public TreeNode createBinTreeByHand() {
        TreeNode a = new TreeNode('a');
        TreeNode b = new TreeNode('b');
        TreeNode c = new TreeNode('c');
        TreeNode d = new TreeNode('d');
        TreeNode e = new TreeNode('e');
        TreeNode f = new TreeNode('f');
        TreeNode g = new TreeNode('g');

        a.left = b;
        b.left = c;
        b.right = d;
        d.left = e;
        e.right = g;
        d.right = f;

        return a;
    }

    /**
     * 2.根据先序遍历和叶子节点的孩子创建 二叉树
     * @param s 先序遍历结果和叶子的孩子
     * @return 根节点
     */
    public TreeNode createBinTreeByPreOrderAndLeaf(String s) {
        /*
        ==》递归出口 每一次都是取出 第一个元素
        ==》剪枝：无
        ==》创建根节点
        ==》递归创建左右子树（递归的递）==》下标变动
        ==》递归的归：return root;
         */

        //存放下标的变动 用于每一次存放下标的时候下标后移++的值
        int[] index = new int[1];
        return createBinTreeNode(s, index);
    }

    private TreeNode createBinTreeNode(String s, int[] index) {
        //递归出口(递归结束的条件) 基本出口：防止你一开始输入就是为null的
        if (index[0] >= s.length()) {//最大的下标是s.length-1
            return null;
        }
        //递归代码
        //取出根节点（第一个元素）
        char ch = s.charAt(index[0]);
        //取出后要将下标后移
        index[0]++;
        //递归剪枝：如果值是#那么就直接返回null
        if(ch == '#') {
            return null;
        }
        //程序走到这里说明==》不是#
        //创建根节点
        TreeNode root = new TreeNode(ch);

        //递归的递：有返回值用于整合递归结果
        root.left = createBinTreeNode(s, index);
        root.right = createBinTreeNode(s, index);

        //递归的归
        return root;
    }

    /**
     * 3.根据前序和后序创建 二叉树
     * @param preorder 前序
     * @param inorder 中序
     * @return 根节点
     */
    public TreeNode createBinTreeByPreOrderAndInOrder(char[] preorder, char[] inorder){
        //递归出口==》基本出口
        if (preorder.length == 0 || inorder.length == 0) {
            //每一次都切割前序和后序 他们同大小 因为来自于用一颗树
            return null;
        }
        //递归剪枝：无

        //递归代码
        //根据前序找到根节点
        char rootNum = preorder[0];
        //创建根节点
        TreeNode root = new TreeNode(rootNum);

        //由根节点的值找到==》中序中的跟节点位置==》从而确定左右子树的个数
        for (int i = 0; i < inorder.length; i++) {
            if (rootNum == inorder[i]) {
                //切割出中序左右子树==》用于确定前序左右子树==》从而前左中左 前右中右 创建子树
                //切割中序子树使用范围思想【已知终点】
                char[] inLeft = Arrays.copyOfRange(inorder, 0, i);//[0, i-1]
                char[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);//[i+1,inorder.length-1]

                //切割中序使用偏移量思想求终点【未知终点】[1+inLeft.length]==>从1往后数inLeft.length到达1+inLeft.length
                char[] preLeft = Arrays.copyOfRange(preorder, 1, 1+inLeft.length);//[1,inLeft.length] 取到inLeft.length处，但是下标在1+inLeft.length
                //起点是上一个下标所指处：1+inLeft.length (下标始终指向的是最后一个的下一个)
                char[] preRight = Arrays.copyOfRange(preorder, inLeft.length + 1, preorder.length);

                //递归创建子树
                root.left = createBinTreeByPreOrderAndInOrder(preLeft, inLeft);
                root.right = createBinTreeByPreOrderAndInOrder(preRight, inRight);
                //找到就退出
                break;
            }
        }
        return root;
    }

    /**
     * 4.根据中序和后序创建二叉树
     * @param inorder 中序
     * @param postorder 后序
     * @return 根节点
     */
    public TreeNode createBinTreeByInOrderAndPostOrder(char[] inorder, char[] postorder) {
        if (inorder.length == 0 || postorder.length == 0) {
            return null;
        }
        //递归代码
        char rootNum = postorder[postorder.length - 1];
        //创建根节点
        TreeNode root = new TreeNode(rootNum);
        for (int i = 0; i < inorder.length; i++) {
            if (rootNum == inorder[i]){
                char[] inLeft = Arrays.copyOfRange(inorder, 0, i);
                char[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);

                //终点：从0开始往后数inLeft.length 最终指针停留在inLeft.length处 取值取到inLeft.length-1
                char[] postLeft = Arrays.copyOfRange(postorder, 0, (0 + inLeft.length));
                char[] postRight = Arrays.copyOfRange(postorder, inLeft.length, postorder.length-1);

                root.left = createBinTreeByInOrderAndPostOrder(inLeft, postLeft);
                root.right = createBinTreeByInOrderAndPostOrder(inRight, postRight);
                break;
            }
        }
        return root;
    }
    /////////////////////////////////////////////////////////////

    //二叉树 的遍历
    ////////////////////////////////////////////////////////////

    /**
     * 1.递归实现前序遍历
     * @param root 根节点
     */
    public void preOrderByRec(TreeNode root) {
        //递归出口：基本出口 安全出口
        if (root == null) {
            return;
        }
        //递归剪枝：无
        //递归代码：
        //先处理根
        System.out.print(root.val + " ");
        //递归入口（递归的递）
        preOrderByRec(root.left);
        preOrderByRec(root.right);
        //递归的归:return void;
    }

    /**
     * 2.递归实现中序遍历
     * @param root 根节点
     */
    public void inOrderByRec(TreeNode root) {
        //递归出口：基本出口 安全出口
        if (root == null) {
            return;
        }
        //递归剪枝：无
        //递归代码：

        //递归入口（递归的递）
        inOrderByRec(root.left);
        //再处理根
        System.out.print(root.val + " ");

        inOrderByRec(root.right);
        //递归的归:return void;
    }

    /**
     * 3.递归实现后序遍历
     * @param root 根节点
     */
    public void postOrder(TreeNode root) {
        //递归出口
        if (root == null) {
            return;
        }
        //递归剪枝：无
        //递归的递
        postOrder(root.left);
        postOrder(root.right);
        //递归核心代码
        System.out.print(root.val + " ");
        //递归的归 return void;
    }

    /**
     * 4.循环实现前序遍历
     * @param root 根节点
     */
    public void preOrderByCir(TreeNode root){
        //使用栈记住来时路
        Deque<TreeNode> stack = new LinkedList<>();
        //从根开始遍历
        TreeNode cur = root;
        //记住上一次出栈过的
        TreeNode pre = root;
        //指针停留在叶子的孩子
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {//去
                //记住来时路
                stack.push(cur);
                System.out.print(cur.val + " ");
                //向左走
                cur = cur.left;
            } else {//来
                TreeNode peek = stack.peek();//瞄一眼
                if (peek.right != null && pre != peek.right) {
                    //如果有右边就往右走
                    cur = peek.right;
                } else {
                    pre = stack.poll();
                }
            }
        }
    }
    /**
     * 5.循环实现中序遍历
     * @param root 根节点
     */
    public void inOrderByCir(TreeNode root){
        //使用栈记住来时路
        Deque<TreeNode> stack = new LinkedList<>();
        //从根开始遍历
        TreeNode cur = root;
        //记住上一次出栈过的
        TreeNode pre = root;
        //指针停留在叶子的孩子
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {//去
                //记住来时路
                stack.push(cur);
                //向左走
                cur = cur.left;
            } else {//来
                TreeNode peek = stack.peek();//瞄一眼
                if (peek.right != null && pre != peek.right) {
                    //中序的话在处理右边之前进行处理节点
                    System.out.print(peek.val + " ");
                    //如果有右边就往右走
                    cur = peek.right;
                } else {
                    //到这里：peek.right == null || 右边已经走过了 此时无论怎样都是代表右边已经处理过了
                    //那么中序的话：只是输出右边为空的情况，而右边已处理是不可以输出的 因为左根右
                    if(pre != peek.right){//如果右边还没处理就输出就OK了
                        System.out.print(peek.val + " ");
                    }
                    pre = stack.poll();
                }
            }
        }
    }
    /**
     * 6.循环实现后序遍历
     * @param root 根节点
     */
    public void postOrderByCir(TreeNode root){
        //使用栈记住来时路
        Deque<TreeNode> stack = new LinkedList<>();
        //从根开始遍历
        TreeNode cur = root;
        //记住上一次出栈过的
        TreeNode pre = root;
        //指针停留在叶子的孩子
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {//去
                //记住来时路
                stack.push(cur);
                //向左走
                cur = cur.left;
            } else {//来
                TreeNode peek = stack.peek();//瞄一眼
                if (peek.right != null && pre != peek.right) {
                    //如果有右边就往右走
                    cur = peek.right;
                } else {
                    //到这里：peek.right == null || 右边已经走过了 此时无论怎样都是代表右边已经处理过了
                    //所以直接输出就好了
                    System.out.print(peek.val + " ");
                    pre = stack.poll();
                }
            }
        }
    }

    /**
     * 7.层序遍历
     * @param root 根节点
     */
    public void levelOrder(TreeNode root) {
        //使用队列：出父入孩子
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            //出父
            TreeNode pop = queue.poll();
            System.out.print(pop.val + " ");

            //入孩子
            if (pop.left != null) {
                queue.offer(pop.left);
            }
            if (pop.right != null) {
                queue.offer(pop.right);
            }
        }
    }

    /**
     * 8.层序遍历的扩展
     * @param root 根节点
     * @return 二维集合
     */
    public List<List<Character>> levelOrderExtend(TreeNode root) {
        List<List<Character>> lists = new LinkedList<>();
        if (root == null) {//安全校验
            return lists;
        }
        //借助队列进行层序遍历==》出父入孩子
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            //首先计算出队列中的元素==》用于每层的元素个数的表示
            int size = queue.size();
            //用于存放每一层
            List<Character> list = new LinkedList<>();
            //出队每一此出父都是同一层的 由size来表示
            while (size > 0) {
                //出父
                TreeNode pop = queue.poll();
                list.add(pop.val);
                //入孩子
                if (pop.left != null) {
                    queue.offer(pop.left);
                }
                if (pop.right != null) {
                    queue.offer(pop.right);
                }
                size--;
            }
            lists.add(list);
        }
        return lists;
    }
    ////////////////////////////////////////////////////////////

    //二叉树的相关OJ
    ////////////////////////////////////////////////////////////

    /****************1.一棵树中的子树****************/
//    public boolean isSameTree(TreeNode p, TreeNode q) {
//        //第一步：安全校验
//        if (p == null && q == null) {
//            return true;
//        }
//        //到这里：p!=null || q!=null
//        if (p == null) {//p == null&&q!=null
//            return false;
//        }
//
//        if (q == null) {//q == null&&p != null
//            return false;
//        }
//        //到这里 p!=null && q!=null
//        //那么此时就看结构：由左右子树的情况
//        if (p.left != null && q.left == null ||
//                p.left == null && q.left != null) {
//            return false;
//        } else if(p.right != null && q.right == null ||
//                p.right == null && q.right != null) {
//            return false;
//        } else {
//            //到这里说明 p.left != null && q.left != null
//            // p.right != null && q.right != null
//            //结构相同那么就比较左右子树的值
//            if (p.val != q.val) {
//                return false;
//            } else {//值相同
//                //那么此时就比较左右子树是否相同
//                return  (isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
//            }
//        }
//    }
//    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//        //首先安全校验
//        if (root == null && subRoot == null) {
//            return true;
//        }
//        //到这里==》root !=null || subRoot != null
//        if (root == null){//root == null && subRoot != null
//            return false;
//        }
//        if (subRoot == null) {//root != null && subRoot == null
//            return true;
//        }
//        //到这里 root != null && subRoot != null
//        //那么此时在root中找到subRoot的根
//
//        TreeNode find = findValue(root, subRoot.val);
//        if (find == null) {
//            return false;
//        }
//        //到这里就是找到了值
//        //那么就是判断 两颗树是否相同
//        boolean isSame = isSameTree(find, subRoot);
//        if (isSame) {
//            return true;
//        }
//        return false;
//    }
//
//    private TreeNode findValue(TreeNode root, int val) {
//        //安全检验==》递归出口
//        if (root == null) {
//            return null;
//        }
//        //递归剪枝：找到就提前结束递归
//        if (root.val == val) {
//            return root;//找到就直接返回了
//        }
//        //递归的递
//        TreeNode left = findValue(root.left, val);
//        if (left != null) {
//            return left;
//        }
//        TreeNode right =findValue(root.right, val);
//        if (right != null) {
//            return right;
//        }
//        //递归的归
//        //到这里说明左右都没有找到
//        return null;
//    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //第一步：安全校验
        if (p == null && q == null) {
            return true;
        }
        //到这里：p!=null || q!=null
        if (p == null) {//p == null&&q!=null
            return false;
        }

        if (q == null) {//q == null&&p != null
            return false;
        }
        //到这里 p!=null && q!=null
        //那么此时就看结构：由左右子树的情况
        if (p.left != null && q.left == null ||
                p.left == null && q.left != null) {
            return false;
        } else if(p.right != null && q.right == null ||
                p.right == null && q.right != null) {
            return false;
        } else {
            //到这里说明 p.left != null && q.left != null
            // p.right != null && q.right != null
            //结构相同那么就比较左右子树的值
            if (p.val != q.val) {
                return false;
            } else {//值相同
                //那么此时就比较左右子树是否相同
                return  (isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
            }
        }
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //首先安全校验
        if (root == null && subRoot == null) {
            return true;
        }
        //到这里==》root !=null || subRoot != null
        if (root == null){//root == null && subRoot != null
            return false;
        }
        if (subRoot == null) {//root != null && subRoot == null
            return true;
        }
        //到这里 root != null && subRoot != null
        //那么此时先看root 与 subRoot是否相同
        //递归的剪枝：如下
        boolean same = isSameTree(root, subRoot);
        if (same) {
            return true;
        }
        //递归的递
        //那么看subRoot是不是root的左子树
        same = isSubtree(root.left, subRoot);
        if (same) {
            return true;
        }
        //到这里不是左子树 那么就看是不是右子树
        same = isSubtree(root.right, subRoot);
        if (same) {
            return true;
        }
        //到这里如果不是左右子树就直接不是子树
        return false;
    }
    /*********************end****************/

    /**
     * 2.反转二叉树
     * @param root 根节点
     * @return 反转后的 二叉树
     */
    public TreeNode invertTree(TreeNode root) {
        //如果节点为空，那么还反转个毛线啊
        if (root == null) {
            return null;
        }
        //子问题的核心代码
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        //子问题(递归的归)
        root.left = invertTree(root.left);
        root.right = invertTree(root.right);

        return root;
    }

    /**
     * 3、判断一棵树是否为平衡二叉树
     * @param root 根节点
     * @return true:是平衡二叉树  false：不是平衡二叉树
     */
    public boolean isBalanced(TreeNode root) {
        //第一步：递归的出口
        if (root == null) {
            return true;
        }
        //递归的核心代码
        int heightDif = Math.abs(treeHeight(root.left) - treeHeight(root.right));
        if (heightDif <= 1) {
            //如果当前节点的左右子树高度差<=1
            //那么就往左右子树走
            return isBalanced(root.left) && isBalanced(root.right);
        }
        return false;
    }

    /**
     * 辅助方法就树的高度
     * @param root 根节点
     * @return 返回树的高度
     */
    private int treeHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHei = treeHeight(root.left);
        int rightHei = treeHeight(root.right);
        return Integer.max(leftHei, rightHei) + 1;
    }

    /**
     * 4、判断 二叉树 是不是对称二叉树
     * @param root 根节点
     * @return true-是  false-不是
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        //特殊情况(也算是剪枝)：调试跳出来：如果只有一个节点，那么说明也是对称的
        if (root.left == null && root.right == null) {
            return true;
        }
        //递归的核心代码
        //第一：确保结构相同
       if (root.left == null) {// root.left == null && root.right != null
            return false;
        } else if( root.right == null){//root.left != null && root.right == null
            return false;
        } else {
            //到这里说明 左右孩子都不为空
            //那么就比较数值
            if (root.left.val == root.right.val) {
                //那么此时就看左右子树是否对称
                return isSymmetricOfChildTree(root.left, root.right);
            }
        }
        return false;
    }

    /**
     * 判断左右孩子是否相同
     * @param left 左孩子
     * @param right 右孩子
     * @return true 同  false 不同
     */
    private boolean isSymmetricOfChildTree(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if(left == null) {
            return false;
        } else if(right == null) {
            return false;
        } else {
            if (left.val == right.val) {
                //那么此时就看左右子树是否对称
                return isSymmetricOfChildTree(left.left, right.right) &&
                        isSymmetricOfChildTree(left.right, right.left);
            }
        }
        return false;
    }

    /**
     * 5、给定⼀个⼆叉树 找到该树中两个指定节点的最近公共祖先
     * @param root 指定树
     * @param p 节点
     * @param q 节点
     * @return 返回公共祖先
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //首先做安全检验
        if (root == null) {
            return null;
        }
        if (root.val == p.val && root.val == q.val) {
            return root;
        } else if (root.val == p.val){//root.val == p.val && root.val != q.val
            if (findValue(root.left, q.val) || findValue(root.right, q.val)) {
                return root;
            }
        } else if (root.val == q.val) {//root.val != p.val && root.val == q.val
            //那么此时在子树中找对应的值
            if (findValue(root.left, p.val) || findValue(root.right, p.val)){
                return root;
            }
        } else {//root.val != p.val && root.val != q.val
            if (findValue(root.left, p.val) && findValue(root.right, q.val)) {
                return root;
            }
            if (findValue(root.left, q.val) && findValue(root.right, p.val)) {
                return root;
            }
        }
        //那么接下来就看一下有没有只在左子树中
        //以及有没有只在右子树中
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        if (left != null) {
            return left;
        }
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (right != null) {
            return right;
        }
        return null;
    }

    /**
     * 辅助函数 ：找出对应的值
     * @param root 要查找的树
     * @param val 数值
     * @return true找到了 false没找到
     */
    private boolean findValue(TreeNode root, int val) {
        //安全检验==》递归出口
        if (root == null) {
            return false;
        }
        //递归剪枝：找到就提前结束递归
        if (root.val == val) {
            return true;//找到就直接返回了
        }
        //递归的递
        boolean left = findValue(root.left, val);
        if (left) {
            return true;
        }
        boolean right =findValue(root.right, val);
        if (right) {
            return true;
        }
        //递归的归
        //到这里说明左右都没有找到
        return false;
    }

    public static void main(String[] args) {
        MyBinTree tree = new MyBinTree();
//        char[] pre = {'3', '4', '1', '2', '5'};
//        char[] in = {'1','4', '2', '3', '5'};
//        char[] pre1 = {'4', '1', '2'};
//        char[] in1 = {'1','4', '2'};

        char[] pre = {'3', '5','6','2','7','4','1','0','8'};
        char[] in = {'6', '5','7','2','4','3','0','1','8'};
//        char[] pre1 = {'1'};
//        char[] in1 = {'1'};
        TreeNode p = new TreeNode('5');
        TreeNode q = new TreeNode('4');
        TreeNode root = tree.createBinTreeByPreOrderAndInOrder(pre, in);
        TreeNode treeNode = tree.lowestCommonAncestor(root, p, q);
        System.out.println(treeNode.val);
//        TreeNode subRoot = tree.createBinTreeByPreOrderAndInOrder(pre1, in1);
//        System.out.println(tree.isSubtree(root, subRoot));
    }
    ////////////////////////////////////////////////////////////
}
